index.md (3708B)
1 +++ 2 title = 'A2 Allocator' 3 +++ 4 # A2 Allocator 5 6 ## Basic info 7 - malloc — allocate memory of given size 8 - free — deallocate memory 9 - realloc — extend/shrink previously allocated 10 - calloc — zero-initialised memory 11 12 first layer: 13 - allocator manages virtual memory region (heap) 14 - if free block is available in heap, block is returned 15 16 sometimes run out of space on heap, need more. need to tell OS that more virtual memory is needed — ask OS for more virtual memory using brk() (‘please extend the heap’). mmap() (‘create new virtual region in the address space’) is a generalised brk(). munmap() is undo for mmap(). 17 18 every time you need memory, the mmu will try to translate and get page fault, which is done with page fault handler. 19 20 virtual memory regions are basically contract between OS and application on legal ranges of memory that we can access 21 22 demand paging: 23 1. Program calls brk() to grow its heap 24 25 2. brk() enlarges virtual memory address space. new pages are not mapped onto physical memory. 26 27 3. Program tries to access new memory, processor page faults. 28 29 4. Kernel assigns page frame to process, creates page table entry, and resumes execution. Program lives happily ever after in userland. 30 31 ## Assignment 32 allocate user space allocator. gets memory from kernel, divides that, etc. 33 34 - `void *malloc(size_t size)` — allocate size bytes. alignment should be 8 bytes. 35 - `void free(void *ptr)` — free object starting at ptr 36 - `void *calloc(size_t nmemb, size_t size)` — allocate nmem * size bytes, zeroed out 37 - `void *realloc(void *ptr, size_t size)` — grow object starting at ptr to size bytes, optionally moving allocation if needed. 38 39 requesting memory from kernel 40 - nmap: allocate arbitrary virtual memory areas 41 - brk/sbrk: grow/shrink heap area 42 - `int brk(void *addr)` — set program break (end of heap) to addr (if reasonable) 43 - `void *sbrk(intptr_t increment)` — grow/shrink heap by increment bytes. returns old brk address. 44 45 getting started 46 47 ```c 48 void *mymalloc(size_t size) { 49 return sbrk(size); 50 } 51 ``` 52 53 problems: 54 55 - size unaligned. should be aligned to 8 bytes, so have to add some alignment. minimum of 8 bytes. 56 - free function is empty. it will run out of memory. how implement free function? 57 - determine size of ptr. how big is the object? 58 - mark area as free. then malloc can search free areas first. 59 60 design options 61 in-band list metadata 62  63 64 each node contains metadata (size, next, prev, is_free) and space for the object. 65 66 when freeing, merge with adjacent free areas. 67 avoid fragmentation — non-contiguous free areas. 68 69 list metadata example 70 71 ```c 72 struct obj_metadata { 73 size_t size; 74 struct obj_metadata *next; 75 struct obj_metadata *prev; 76 int is_free; 77 }; 78 ``` 79 80 don’t use artificial limit on max number of objects. should have pointer to heap_start, and pointer to freelist (both void). dynamically grow. would give penalty. 81 82 Grading 83 - 1 point — showing up (valid submission) 84 - 1 point — malloc 85 - 0.5 pnt — calloc 86 - 2 point — free + reuse 87 - 1 point — realloc (+only when needed) 88 - 1 point — batch brk: preallocate e.g. 4K of memory, only brk when 4K is full 89 - 2 point — reduce overhead per allocation (brk size vs malloc’d size) 90 - 0.5 pnt — locality (new allocations use least recently freed slots) 91 - 1 point — return memory to kernel (give negative to sbrk). return reasonable sized (e.g. 4K) chunk at end of heap if became free. 92 - 1 point — out-of-band metadata. e.g. slab allocator. this often excludes other points. 93 - 2 point — system malloc. implement malloc without prefix. use with LD_PRELOAD env var. tests run ls, grep, python.